A service that takes geographical location into account is referred to as a location-based service. Location-based services are particularly compelling in a mobile computing context in which the location of clients and services is constantly changing. Herein lies the opportunity to connect appropriate clients and services based on their respective locations. Example applications include emergency medical services that automatically dispatch the closest ambulance based on the location of the initiating phone call, restaurant directory systems that allow a user to search for the nearest restaurant of a given type and message delivery systems that automatically route electronic messages to a recipient as his/her location varies. Location-based services are an important component of a pervasive computing infrastructure.
Location-based services are at the intersection of several important industries, including but not limited to global position satellite (GPS) technology and mobile communication networks. These two industries provide a framework for supporting location-based services. Trends in these industries make it clear that location-based services will be an increasingly important offering in the near future.
A critical feature of location-based services is the ability to perform spatial queries about geographical regions. I.e., to determine the physical location of computational clients and services with respect to geographical regions. Spatial queries are necessary in facilitating the interaction between a user and a ubiquitous computing system so that a user can determine where computational resources are located. There are two fundamental types of spatial queries: firstly, a determination of what objects are in a region, and secondly, a determination of which region includes one or more objects. The first is herein referred to as the “what is there?” question, as in “what objects are contained within a given geographical region?”. The second is referred to herein as the “where is it?” question as in “what geographical region contains a given object?”.
Spatial queries are a special case of metric queries. A metric space is a set of elements in which there is defined a distance between any pair of elements in the set. Metric queries compare the relative distances of elements in a metric space where elements in the set include regions. Spatial queries are metric queries in which the units of distance measurements include feet, miles, meters, kilometers, or such, and in which regions are geographical regions. As with spatial queries, metric queries include both “what is there?”, and “where is it?” queries.